

/**
 * 
 * 回溯算法
 * 
 * 回溯法可以看成穷举法的升级版。回溯法非常适合解决由多个步骤组成，并且每个步骤都有多个选项的问题。 当我们在某一步选择了其中一个选项后，就进入下一步，然后又面临新的选项。就这样重复选择，直至最终的状态。

可以用树结构（解空间树）来表示用回溯法解决的问题的所有选项。在某一步有 n n n 个可能的选项，那么该步骤就可以看成是树结构中的一个节点，每个选项看成树中节点的连接线，经过这些连接线到达该节点的 n n n 个子节点。叶节点则对应着最终的状态：

如果在叶节点的状态满足题目的约束条件，那我们就找到了一个问题的解；
如果在叶节点的状态不满足约束条件，那就回溯到它的上一个节点尝试其它的选项；
如果上一个节点所有可能的选项都已经试过，则再回溯到它的上一个节点，直至所有节点的所有选项都尝试过；
如果所有节点的所有选项都已经尝试过却没有找到满足约束条件的最终状态，说明该问题无解。
所以，用回溯法求解问题的过程，就是搜索整个解空间树的过程。当搜索至任一节点时，先判断该节点是否包含问题的解，如果不包含，则跳过该节点的子节点的搜索，避免无效搜索，这个过程叫作 “剪枝”。

Tips：

回溯法求解的特点是在搜索过程中动态产生问题的解空间。在任意时刻，算法只保存从根结点到当前结点的路径。



回溯法：

创建一个和字符矩阵大小相同的布尔型矩阵，记录矩阵中的位置是否走过，走过为 true，没走过则为false；
从 (0, 0) 开始，遍历字符矩阵，先找到字符串的第一个字符在字符矩阵中的位置；
从该位置向左、右、上、下四个方向探索，匹配字符串的下一个字符；
若全部匹配成功，返回 true；否则，回溯至上一步，继续探索，直至遍历完整个字符数组；
探索过程中，要注意边界条件，行和列不能越界。

 * 
 */
public class 矩阵中的路径 {
    
    public static void main(String[] args) {

        

    }

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
        boolean[] flag = new boolean[matrix.length];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(backTrack(matrix, i, j, 0, rows, cols, str, flag))
                    return true;
            }
        }
        return false;
    }

    /**
    i：行坐标
    j：列坐标
    k：字符串的索引，表示当前匹配到第 k 位字符
    rows：行数
    cols：列数
    str：要匹配的字符串
    flag：标志矩阵
    */
    private boolean backTrack(char[] matrix, int i, int j, int k, int rows, int cols, char[] str, boolean[] flag){
        // 计算匹配到的第一个字符在矩阵中的位置
        int index = i * cols + j;
        // 递归结束条件
        if(i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index])
            return false;
        // 当 k = str.length - 1 时，说明整个字符串都匹配到了
        if(k == str.length - 1)
            return true;
        flag[index] = true;
        // 向上下左右四个方向搜索，匹配下一个字符
        if(backTrack(matrix, i - 1, j, k + 1, rows, cols, str, flag) || // 向上
              backTrack(matrix, i + 1, j, k + 1, rows, cols, str, flag) || // 向下
              backTrack(matrix, i, j - 1, k + 1, rows, cols, str, flag) || // 向左
              backTrack(matrix, i, j + 1, k + 1, rows, cols, str, flag)){ // 向右
            return true;
        }
        // 没有匹配到，回溯
        flag[index] = false;
        return false;
    }

}
